《剑指offer》 04.二维数组中的查找

剑指offer
留言

Note：比遍历时间更优的除了二分，还有减治，当然二分就是一种减治的思想，但是减治不一定必须二分。

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例：

现有矩阵 matrix 如下：

1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

1
2
0 <= n <= 1000
0 <= m <= 1000

解法一：暴力

思路

不考虑任何特性，直接遍历每个元素，在限制的条件下，显然也是完全可以接受的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        
        for(const auto &row : matrix){
            for(const auto &el : row){
                if(el==target)
                    return true;
            }
        }
        return false;
    }
};

复杂度

  • 时间复杂度O(MN)。要遍历整个二维数组
  • 空间复杂度 O(1)。没有使用额外空间

解法二：二分查找

思路

由于二维数组是有序的，所以很容易想到二分查找的方法。但是同时我们也很容易发现，一般的二分查找很难满足二维的需求。

我们可以沿着对角线进行二分查找 ，每到一个新的位置，我们可以以当前位置为起始，分别向右、向下进行二分查找。

这样我们可以在一个维度上实现二分，另一个维度上进行遍历，时间效率上会有所改善。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    bool binarySearch(vector<vector<int>>& matrix,int target,int start,bool x){
        int m = matrix.size();
        int n = matrix[0].size();
    
        int fixed = start;
        int end = x ? n-1 : m-1;
        while(start<=end){
            int mid = start+(end-start)/2;
            int num = x ? matrix[fixed][mid]:matrix[mid][fixed];
            if(num==target)
                return true;
            else if(num<target){
                start = mid+1;
            }else{
                end = mid-1;
            }
        }
        return false;
        
    }
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if(m==0)
            return false;   
        int n = matrix[0].size();
        if(n==0)
            return false;

        for(int i=0;i<min(m,n);i++){
            bool foundx = binarySearch(matrix,target,i,true);
            bool foundy = binarySearch(matrix,target,i,false);
            if(foundx || foundy)
                return true;
        }

        return false;
    }
};

ps. 这种写法为了提高代码的复用，做了两次if，所以可能会对时间性能有所影响。

复杂度

  • 时间复杂度$O(lg(n!))$。参考leetcode题解，具体推导过程略。
  • 空间复杂度$O(1)$。没有使用额外空间

解法三：减治线性查找

思路

观察矩阵，矩阵的行列从左到右从上到下分别有序，那么我们可以发现，如果从矩阵的右上角或左下角来看整个矩阵的话，这个矩阵就是一个“二叉搜索树”。以右上方开始为例，我们可以做这样的操作：如果指向的值大于目标值，那么就将指针向左移动，如果指向的值小于目标值，我们就可以将指针向下移动。不断移动指针，直到我们找到目标值，或者指针移出整个矩阵。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if(m==0)
            return false;   
        int n = matrix[0].size();
        if(n==0)
            return false;
        
        int row = 0,col = n-1;

        while(row<m && col>=0){
            if(matrix[row][col]==target)
                return true;
            if(matrix[row][col]<target)
                row++;
            else if(matrix[row][col]>target)
                col--;
        }
        return false;
    }
};

复杂度

  • 时间复杂度$O(n+m)$。指针移动访问，向左移动最多m次，向下移动最多n次。
  • 空间复杂度$O(1)$。没有使用额外空间